package letcode.oneQuestionPerDay._202003._20200321;

/**
 * @author 许群星
 * @decription  水壶问题   数学方法
 * @data 2020/3/218:20
 **/
public class WaterAndJugProblem_1 {
    public static void main(String[] args) {
//        int x=3,y=5,z=4;
//        int x=2,y=6,z=5;
        int x=11,y=13,z=3;
        System.out.println(canMeasureWater(x,y,z));
    }
    //提供方法
    public static boolean canMeasureWater(int x, int y, int z) {
       //贝祖定理： ax+by=z有解，当前仅当z是x，y的最大公约数的倍数。
        if (x+y<z)
            return false;
        if (x==0||y==0)
            return z==0||x+y==z;
        return z%gcd(x, y)==0;
    }
    //求最大公约数
    public static int gcd(int x,int y){
        int res=0;
        while (y!=0){
            res=x%y;
            x=y;
            y=res;
        }
        return x;
    }
}
/*
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)

输入: x = 3, y = 5, z = 4
输出: True
示例 2:

输入: x = 2, y = 6, z = 5
输出: False
 */